% \section{Otimização}
% 
% \subsection{Crivo para Quadrados Perfeitos}
% 
% É possível chegar ao resultado de que todo quadrado perfeito par é
% múltiplo de$4$, todo quadrado perfeito ímpar deixa resto$1$mod$4$e, por
% transitividade,$1$mod$8$.
% Analisando o digito menos significativo, e o seu quadrado, dos múltiplos de 4 e
% dos ímpares que deixam resto$1$na divisão por$4$, chega-se a conclusão que os
% quadrados perfeitos só podem ter os algarismos$0, 1, 4, 5, 6$e$9$como digito
% menos significativo.
% 
% A partir dessa ideia, pode-se criar um crivo inicial que retorna
% \textsc{falso} para qualquer candidato a quadrado perfeito que termine em$2,
% 3, 7$ou$8$.
% 
% \subsection{Multiplicação de Karatsuba}
% 
% Anatolii A. Karatsuba, quando jovem aluno de graduação, propôs um
% eficiente algoritmo para multiplicação~\cite{karat63} de dois números grandes que
% contradizia uma conjectura lançada por seu professor, A. Kolmogorov, a respeito de um limite
% inferior para essa multiplicação. A mesma ideia de Karatsuba pode ser aplicada na
% multiplicação de polinômios: 
%$a\cdot b = \big[(a_1+a_0)(b_1+b_0)-a_1b_1 -a_0b_0 \big]x +a_0b_0 + a_1b_1c$.
% 
% Expandindo essa expressão de Karatsuba, pode-se notar que retorna ao mesmo
% resultado da multiplicação em~\ref{basic-arit}. Assim, reutilizando os produtos
% já computados, o custo da multiplicação de dois polinômios cai para três multiplicações e uma redução.
% 
% \subsection{Fórmula do Quadrado Complexo}
% 
% Também se tem uma expressão utilizada no quadrado de número complexos,$(a +
% bi)$, que pode ser usada no quadrado de polinômios quadráticos: 
%$a^2 = 2a_0a_1x + (a_0 + a_1)(a_0 + a_1c) - a_0a_1 - a_0a_1c$.
% O custo é reduzido para apenas duas multiplicações:$(a_0 + a_1)(a_0 + a_1c)$e
%$a_0 a_1$.
% 
% \subsection{Janela Deslizante}
% 
% O método janela deslizante para exponenciação modular implementado é baseado em
% uma generalização do algoritmo de exponenciação esquerda para direita que
% possibilita o processamento de mais de um \emph{bit} do expoente por iteração através do
% pré-cálculo de exponenciações em uma janela. A janela deslizante consegue
% reduzir o pré-cálculo e a quantidade de multiplicações~\cite{menezes96}.
% 
% \subsection{Redução de Montgomery}
% 
% Durante a exponenciação modular, são realizadas sucessivas multiplicações e
% quadrados. As repetidas reduções em$\mathbb{Z}_n$nessas
% operações é um fator limitante crítico do desempenho da função.
% Uma solução proposta por Montgomery é trocar as divisões por
% multiplicações.
% Contudo, há um detalhe importante: para ser realizada a redução de
% Montgomery é necessário o pré-cálculo de uma
% inversão em$\mathbb{Z}_n$, fato que deve ser considerado na análise do desempenho.
% 
% A otimização é alcançada quando é necessário uma repetição conhecida de
% operações que utilizam essa redução. Neste caso, a transformação na forma de
% Montgomery pode ser antecipada e a volta, atrasada para depois das repetições,
% aumentando o desempenho nas reduções.
% 
% 
% \subsection{Mudança Algébrica}
% 
% \subsubsection{Multiplicação por$c$pequeno}
% 
% Analisando o algoritmo~\ref{alg:mr2} (MR2), vê-se que o inteiro retornado$c$
% varia em apenas três casos:$c = -1 \equiv n-1$,$c = 2$e$c =$valor
% aleatório pequeno tal que$(c/n) = -1$.
% As multiplicações de inteiros multi-precisão por$c$podem ser simplificadas
% para todos os casos.
% 
% No primeiro caso, podemos trocar uma multiplicação de$n-1$e uma redução módulo
%$n$por apenas uma subtração de$n$.
% No segundo caso, trocamos uma multiplicação
% e uma redução por um \emph{shift left} e uma subtração.
% Para o terceiro caso, podemos trocar a busca aleatória por uma busca incremental
% com no máximo 3 cálculos de Jacobi~\cite{sqft}, assim mantendo o valor de$c$
% restritamente pequeno de modo que possamos substituir uma multiplicação e uma
% redução por uma multiplicação por dígito simples e$O(1)$subtrações.
% 
% 
% \subsubsection{Reuso de uma exponenciação modular}
% 
% É possível reduzir a quantidade de exponenciações modulares necessárias nos
% cálculos de$z^n$e$z^{(n^2-1)/8}$no algoritmo TFQS~\cite{sqft}.
% Tome$t = z^{\lfloor(n-1)/8\rfloor} = z^{(n-1-\epsilon)/8}$,$\epsilon \in
% \mathbb{Z}$e$0 \leq \epsilon < 8$. Computando$t$previamente e definindo
%$\epsilon$, podemos calcular$z^n$com mais$O(1)$multiplicações e quadrados. A
% partir de$t$, também podemos obter o valor de$z^{(n^2-1)/8}$como segue:
%$z^{(n^2-1)/8} =
% z^{(n+1+\epsilon)(n-1-\epsilon)/8}\cdot z^{\epsilon(\epsilon+2)/8} =
% N(t)\cdot t^{\epsilon}\cdot z^{\epsilon(\epsilon+2)/8}.$Assim, de duas
% exponenciações modulares em anel polinomial é possível reduzir para apenas uma
% exponenciação e$O(1)$multiplicações e quadrados.
% 
% 
% \subsection{Redução Preguiçosa}
% 
% Entre as três multiplicações na implementação de Karatsuba é necessária uma
% redução modular extra para que não seja excedida a precisão da biblioteca, no
% caso dos operandos terem precisão máxima.
% 
% A técnica da redução preguiçosa consiste em atrasar esta redução intermediária
% para o final da operação:
% \begin{itemize}
%   \item Elimina-se a redução intermediária e define um fator de redução$r = n
%   \cdot 2^{|n|}$.
%   \item Quando necessária uma soma ou subtração de um produto com a
%   precisão acumulada, realiza-se uma soma ou subtração de$r$como redução.
% \end{itemize}
% 
% O custo final da multiplicação de Karatsuba em $I(n,c)$ é de três
% multiplicações e duas reduções. Na operação de quadrado não há como usar a técnica da redução
% preguiçosa, pois o cenário ja é ótimo, duas multiplicações e duas reduções modulares.


\section{Optimization} 

\subsection{Sieve for Perfect Squares}

It is possible to reach the result that every even perfect square is 
multiple of $4$, every odd perfect square leaves remainder $1$ mod $4$ and, 
by transitivity, $1$ mod $8$. 
Analyzing the least significant digit, and its square, of multiples of 4 and 
the odds that leaves remainder $1$ on division by $4$ , it is deduced that
perfect squares can only have $0, 1, 4, 5, 6$ and $9$ as last digit.

From this view, can created an initial sieve that outputs 
\textsc{false} for any perfect square candidate that has last digit $2, 
3, 7$ or $8$. 

\subsection{Karatsuba Multiplication}

Anatolii A. Karatsuba, as a young graduate student, proposed a 
efficient algorithm for large numbers multiplication~\cite{karat63},
contradicting a conjecture thrown by his professor, A. Kolmogorov, about a
lower limit for this very multiplication. The same Karatsuba idea can be
applied in polynomials multiplication:

$a\cdot b = \big[(a_1+a_0)(b_1+b_0)-a_1b_1 -a_0b_0 \big]x +a_0b_0 + a_1b_1c$.

Expanding Karatsuba expression, it may be noted that returns to
the same result of the multiplication in~\ref{basic-arit}. Thus, reusing
products already calculated, the multiplication cost of two polynomials falls to three
multiplications and one reduction.

\subsection{Complex Square Formula} 

Likewise, there is an expression for complex square numbers, $(a + bi)$, which
can be used in quadratic polynomials square:

$a^2 = 2a_0a_1x + (a_0 + a_1)(a_0 + a_1c) - a_0a_1 - a_0a_1c$.

The operation cost is reduced to only two multiplications: $(a_0 + a_1) (a_0 +
a_1c)$ and $a_0 a_1$.

\subsection{Sliding Window}

The sliding window method implemented for modular exponentiation is
based on a generalization of left-to-right exponentiation algorithm that 
enables processing more than one bit of the exponent for iteration through 
precomputation exponentiations in a window. The sliding window can 
reduce this precalculation and the total multiplications~\cite{menezes96}. 

\subsection{Montgomery Reduction} 

During modular exponentiation, successive multiplications and 
square are executed. Repeated reductions in $\mathbb{Z}_n$ of these 
operations is a critical limiting factor of functions performance.
A solution proposed by Montgomery is switching divisions for 
multiplications. 
However, there is one important detail: To perform a Montgomery reduction, it
is necessary a precalculation of a inversion in $\mathbb{Z} _n$ , a fact that
must be considered when analyzing performance.

The optimization is achieved when a known operations repetition which use this
reduction  is necessary. In this particular case,
Montgomery form transformation can be anticipated and the turn back, delayed
after the repetitions, increasing great performance in the reductions.

\subsection{Algebraic Change} 

\subsubsection{Multiplying by small $c$} 

Analyzing the algorithm~\ref{alg:mr2} (MR2), can be observed that the output
integer $c$ varies in three cases only: $c = -1 \equiv n-1$, $c = 2$ and $c
=$ small random value such that$(c / n) = -1$.
The multiplication of multi-precision integers by $c$ can be simplified for all
cases.

In the first case, we can replace a multiplication by $n-1$ and a reduction 
modulus $n$ for just a subtraction of $n$.
In the second case, we exchanged a multiplication and a reduction for a
left shift and a subtraction.
For the third case, we can replace the random search for an incremental search
with a maximum of 3 Jacobi computations~\cite{sqft}, thus maintaining the $c$
value restrictively small so that we can replace a multiplication and a
reduction by a simple multiplication by digit and $O(1)$ subtractions.

\subsubsection{Reuse of a modular exponentiation} 

As well, it is possible to reduce the number of modular exponentiations required
in the computation of $z ^ n$ and $z ^{(n ^ 2-1) / 8}$ in algorithm
SQFT~\cite{sqft}.

Take $t = z^{\lfloor(n-1)/8\rfloor} = z^{(n-1-\epsilon)/8}$, $\epsilon \in
\mathbb{Z}$ and $0 \leq \epsilon <8$. Computing $t$ in advance and setting
$\epsilon$, we calculate $z ^ n$ over $O(1)$ multiplications and squares. From
$t$ , we can also obtain the value of $z^{(n^2-1) / 8}$ as follows:

$z^{(n^2-1)/8} = z^{(n+1+\epsilon)(n-1-\epsilon)/8}\cdot
z^{\epsilon(\epsilon+2)/8} = N(t)\cdot t^{\epsilon}\cdot
z^{\epsilon(\epsilon+2)/8}.$

Hence, from two 
modular exponentiation in polynomial ring it can be reduced to only one 
exponentiation and $O(1)$ multiplications and squares. 


\subsection{Lazy Reduction}

Among the three multiplications in Karatsuba implementation it is
required an extra modular reduction so the precision of the library is not
exceeded, in case operands have maximum size.

The lazy reduction technique consists in delaying this intermediate reduction to
the end of the operation:

\begin{itemize}
	\item Discard the intermediate reduction and defines a
	reduction factor $r = n \cdot 2^{|n|}$.
	\item When required an addition or subtraction of a product with cumulative
	precision, we make an addition or subtraction of $r$ as reduction.
\end{itemize} 

The final cost of the Karatsuba multiplication in $R(n, c)$ is three
multiplications and two reductions. In squaring operation can not use the
lazy reduction technique, because the scenery is already optimum, two
multiplications and two modular reductions.
